package TreePackage;

/**
 * @author Lzm
 * @version 1.0
 * 二叉树
 */
public class BinaryTree {
  public static void main(String[] args) {
    BinaryTree tree = new BinaryTree();
    heroNode heroNode1 = new heroNode(1, "1");
    heroNode heroNode2 = new heroNode(2,"2");
    heroNode heroNode3 = new heroNode(3,"3");
    heroNode heroNode4 = new heroNode(4,"4");
    heroNode heroNode5 = new heroNode(5,"5");
    tree.setRoot(heroNode1);
    tree.root.setLeft(heroNode2);
    tree.root.setRight(heroNode3);
    heroNode3.setRight(heroNode4);
    heroNode3.setLeft(heroNode5);
    /*测试前序遍历*/
    tree.preList();
    System.out.println("=============");
    /*测试中序遍历*/
    tree.middleList();
    System.out.println("=============");
    /*测试后序遍历*/
    tree.lastList();
    System.out.println("=============");

    /*测试前序查找*/
    System.out.println(tree.preFind(1));
    System.out.println("=============");
    System.out.println(tree.middleFind(1));
    System.out.println("=============");
    System.out.println(tree.lastFind(1));
    System.out.println("=============");
  }

  public heroNode root;

  public BinaryTree() {
  }

  public BinaryTree(heroNode root) {
    this.root = root;
  }

  /**
   * 获取
   * @return root
   */
  public heroNode getRoot() {
    return root;
  }

  /**
   * 设置
   * @param root
   */
  public void setRoot(heroNode root) {
    this.root = root;
  }

  public String toString() {
    return "BinaryTree{root = " + root + "}";
  }

  /*定义前序遍历方法*/
  public void preList(){
    if (this.root == null){
      throw new RuntimeException("树为空");
    }
    this.root.preList();
  }

  /*定义中序遍历方法*/
  public void middleList(){
    if (this.root == null){
      throw new RuntimeException("树为空");
    }
    this.root.middleList();
  }

  /*定义后序遍历方法*/
  public void lastList(){
    if (this.root == null){
      throw new RuntimeException("树为空");
    }
    this.root.lastList();
  }

  /*定义前序查找*/
  public heroNode preFind(Integer no){
    if (this.root == null){
      throw new RuntimeException("树为空");
    }
    return this.root.preFind(no);
  }

  /*定义中序查找*/
  public heroNode middleFind(Integer no){
    if (this.root == null){
      throw new RuntimeException("树为空");
    }
    return this.root.middleFind(no);
  }

  /*定义后序查找*/
  public heroNode lastFind(Integer no){
    if (this.root == null){
      throw new RuntimeException("树为空");
    }
    return this.root.lastFind(no);
  }


}
class heroNode{
  private int no;
  private String name;
  private heroNode left;
  private heroNode right;

  public heroNode() {
  }

  public heroNode(int no, String name) {
    this.no = no;
    this.name = name;
  }

  /**
   * 获取
   * @return no
   */
  public int getNo() {
    return no;
  }

  /**
   * 设置
   * @param no
   */
  public void setNo(int no) {
    this.no = no;
  }

  /**
   * 获取
   * @return name
   */
  public String getName() {
    return name;
  }

  /**
   * 设置
   * @param name
   */
  public void setName(String name) {
    this.name = name;
  }

  /**
   * 获取
   * @return left
   */
  public heroNode getLeft() {
    return left;
  }

  /**
   * 设置
   * @param left
   */
  public void setLeft(heroNode left) {
    this.left = left;
  }

  /**
   * 获取
   * @return right
   */
  public heroNode getRight() {
    return right;
  }

  /**
   * 设置
   * @param right
   */
  public void setRight(heroNode right) {
    this.right = right;
  }

  public String toString() {
    return "heroNode{no = " + no + ", name = " + name + "}";
  }
  /*定义前序遍历方法*/
  public void preList(){
      /*进行前序遍历*/
      System.out.println(this);
      /*遍历左子树左子树*/
      if (this.left != null){
        this.left.preList();
      }
    /*遍历左子树左子树*/
      if (this.right != null){
        this.right.preList();
      }
  }
  /*定义中序遍历方法*/
  public void middleList(){
    /*进行中序遍历*/
    /*遍历左子树左子树*/
    if (this.left != null){
      this.left.middleList();
    }
    System.out.println(this);
    /*遍历左子树左子树*/
    if (this.right != null){
      this.right.middleList();
    }
  }

  /*定义后序遍历方法*/
  public void lastList(){
    /*进行中序遍历*/
    /*遍历左子树左子树*/
    if (this.left != null){
      this.left.lastList();
    }

    /*遍历左子树左子树*/
    if (this.right != null){
      this.right.lastList();
    }
    System.out.println(this);
  }

  /*定义前序查找节点*/
  public heroNode preFind(Integer no){
    System.out.println("前序查找");
    /*判断当前节点是否为要查找的节点*/
    if (this.no == no){
      return this;
    }
    /*判断当前节点的左子节点是否为空*/
    heroNode resultNode = null;
    if (this.left != null){
      resultNode = this.left.preFind(no);
    }
    if (resultNode != null){
      return resultNode;
    }
    /*判断当前节点的右子节点是否为空*/
    if (this.right != null){
      resultNode = this.right.preFind(no);
    }
    if (resultNode != null){
      return resultNode;
    }
    return resultNode;
  }

  /*定义中序查找节点*/
  public heroNode middleFind(Integer no){
    System.out.println("中序查找");
    /*判断当前节点的左子节点是否为空*/
    heroNode resultNode = null;
    if (this.left != null){
      resultNode = this.left.middleFind(no);
    }
    if (resultNode != null){
      return resultNode;
    }
    /*判断当前节点是否为要查找的节点*/
    if (this.no == no){
      return this;
    }
    /*判断当前节点的右子节点是否为空*/
    if (this.right != null){
      resultNode = this.right.middleFind(no);
    }
    if (resultNode != null){
      return resultNode;
    }
    return resultNode;
  }

  /*定义后序查找*/
  public heroNode lastFind(Integer no){
    /*判断当前节点的左子节点是否为空*/
    System.out.println("后序查找");
    heroNode resultNode = null;
    if (this.left != null){
      resultNode = this.left.lastFind(no);
    }
    if (resultNode != null){
      return resultNode;
    }
    /*判断当前节点的右子节点是否为空*/;
    if (this.right != null){
      resultNode = this.right.lastFind(no);
    }
    if (resultNode != null){
      return resultNode;
    }
    /*判断当前节点是否为要查找的节点*/
    if (this.no == no){
      return this;
    }
    return resultNode;
  }
}
